package cn.chen.数据结构.二叉树.线索二叉树;

/**
 * 线索二叉树：按照遍历次序（前序、中序、后序）将节点的左右空指针都指向节点的前驱后继节点。
 */
public class ThreadedBinaryTree {

    private ThreadedTreeNode root;  // 根结点
    private ThreadedTreeNode pre;   // 用于记录当前节点的前驱结点。初始值为null

    public void setRoot(ThreadedTreeNode root) {
        this.root = root;
    }
    public ThreadedTreeNode getRoot() {
        return root;
    }



    // 重载遍历中序线索化方法2
    public void midOrder2(){

        this.midOrder2(root);
    }

    // 遍历中序线索化方法2
    public void midOrder2(ThreadedTreeNode node){

        if(node==null)
            return;

        // 遍历左子树
        if(node.leftNode!=null&&node.leftType==0)
            midOrder2(node.leftNode);

        // 输出当前节点
        System.out.println(node);


        // 遍历右子树
        if(node.rightNode!=null&&node.rightType==0)
            midOrder2(node.rightNode);

    }

    // 遍历中序线索化方法1
    public void midOrder1(){

        ThreadedTreeNode node=root;
        while (node!=null){

            // 往左循环找，直到找到指向前驱节点的节点，
            while (node.leftType==0)
                node=node.leftNode;

            // 输出该结点
            System.out.println(node);

            // 如果当前节点指向的是后继节点，就一直输出
            while (node.rightType==1){

                node=node.rightNode;    // 将node往后移动
                System.out.println(node);
            }
            // 替换这个遍历的节点
            node=node.rightNode;
        }
    }

    // 重载中序
    public void midClueing(){

        pre=null;
        this.midClueing(root);
    }

    // 中序线索化
    private void midClueing(ThreadedTreeNode node){

        // 如果node=null 那么就不用线索化该节点了
        if(node==null)
            return;

        // 1、 对左子树进行线索化
        midClueing(node.leftNode);

        // 2、 对当前节点进行线索化
        // 处理当前节点的前驱结点
        if(node.leftNode==null){

            node.leftNode=pre;  // 将当前节点的左指针指向前驱结点
            node.leftType=1;    // 设置当前节点的左指针的状态为1，指向前驱结点
        }

        // 处理当前节点的后继节点
        // 这里以pre来做的，因为这时候node已经是下一个节点了，而且pre是node的前驱结点
        if(pre!=null&&pre.rightNode==null){

            pre.rightNode=node;
            pre.rightType=1;
        }

        // 每次线索化一个节点之后，让当前节点是下一个节点的前驱结点。
        pre=node;

        // 3、 对右子树进行线索化
        midClueing(node.rightNode);
    }
    public void postClueing(){

        pre=null;
        this.postClueing(root);
    }
    // 后序线索化
    private void postClueing(ThreadedTreeNode node){

        if(node==null)
            return;

        // 1、线索化左子树
        postClueing(node.leftNode);
        // 2、线索化右子树
        postClueing(node.rightNode);

        // 3、线索化当前节点
        if(node.leftNode==null){

            node.leftNode=pre;
            node.leftType=1;
        }

        if(pre!=null&&pre.rightNode==null){

            pre.rightNode=node;
            pre.rightType=1;
        }

        pre=node;

    }

    public void preClueing(){

        pre=null;
        this.preClueing(root);
    }
    // 前序线索化
    private void preClueing(ThreadedTreeNode node){

        if(node==null)
            return;

        // 1、 对当前节点进行线索化
        if(node.leftNode==null){

            node.leftNode=pre;
            node.leftType=1;
        }

        if(pre!=null&&pre.rightNode==null){

            pre.rightNode=node;
            pre.rightType=1;
        }
        pre=node;

        // 2、 对左子树进行线索化
        if(node.leftType==0)    // 这里需要进行判断该节点的左子树是否是前驱结点，如果不判断会进入死递归
            preClueing(node.leftNode);
        // 3、 对右子树进行线索化
        if(node.rightType==0)
            preClueing(node.rightNode);
    }



    // 判断该二叉树是否为空
    public boolean isEmpty(){

        return this.root==null;
    }
}

